We consider the scheduling of multiple tasks with pre-determined deadlinesunder random processing cost. This problem is motivated by the potential oflarge scale adoption of plug-in (hybrid) electric vehicles (PHEVs) in the nearfuture. The charging requests of PHEVs usually have deadline constraints, andthe electricity cost associated with PHEV charging is usually random due to theuncertainty in both system load and renewable generation. We seek to properlyschedule the battery charging of multiple PHEVs so as to minimize the overallcost, which is derived from the total charging cost and the penalty for notcompleting charging before requested deadlines. Through a dynamic programmingformulation, we establish the Less Laxity and Longer remaining Processing time(LLLP) principle that improves any charging policy on a sample-path basis, whenthe non-completion penalty is a convex function of the additional time neededto fulfill the uncompleted request. Specifically, the LLLP principle statesthat priority should be given to vehicles that have less laxity and longerremaining processing times. Numerical results demonstrate that heuristicpolicies that violate the LLLP principle, for example, the earliest deadlinefirst (EDF) policy, can result in significant performance loss.
展开▼
